package ch4.part3;

import java.util.Arrays;

/**
 * 单侧快速排序，以左侧为准，不稳定排序
 * 平均时间复杂度：O(n) = nlogn
 * 最坏时间复杂度：O(n) = n ^ 2
 * 平均空间复杂度：O(n) = logn
 * @author liuwanxiang
 * @version 2019/05/17
 */
public class LeftCycleQuicklySort {

    public static void main(String[] args) {
        int[] array = {1, 2, 5, 4, 3, 9, 8, 6, 7, 0};
        // int[] array = {4, 7, 6, 5, 3, 2, 8, 1};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * QuickSort算法入口
     *
     * @param array 待排序数组
     */
    private static void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    /**
     * QuickSort的递归方法体
     * --------------------------------------------------------------------------------------------
     * n      => s e array(before)                  => array(after)                   => pivotIndex
     * --------------------------------------------------------------------------------------------
     * 1      => 0 9 [1, 2, 5, 4, 3, 9, 8, 6, 7, 0] => [0, 1, 5, 4, 3, 9, 8, 6, 7, 2] => 1
     *  2     => 0 0 [0, 1, 5, 4, 3, 9, 8, 6, 7, 2] => return;
     *  3     => 2 9 [0, 1, 5, 4, 3, 9, 8, 6, 7, 2] => [0, 1, 2, 4, 3, 5, 8, 6, 7, 9] => 5
     *   4    => 2 4 [0, 1, 2, 4, 3, 5, 8, 6, 7, 9] => [0, 1, 2, 4, 3, 5, 8, 6, 7, 9] => 2
     *    5   => 2 1 [0, 1, 2, 4, 3, 5, 8, 6, 7, 9] => return;
     *    6   => 3 4 [0, 1, 2, 4, 3, 5, 8, 6, 7, 9] => [0, 1, 2, 3, 4, 5, 8, 6, 7, 9] => 4
     *     7  => 4 3 [0, 1, 2, 3, 4, 5, 8, 6, 7, 9] => return;
     *     8  => 5 4 [0, 1, 2, 3, 4, 5, 8, 6, 7, 9] => return;
     *   9    => 6 9 [0, 1, 2, 3, 4, 5, 8, 6, 7, 9] => [0, 1, 2, 3, 4, 5, 7, 6, 8, 9] => 8
     *    10  => 6 7 [0, 1, 2, 3, 4, 5, 7, 6, 8, 9] => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] => 7
     *     11 => 6 6 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] => return;
     *     12 => 8 7 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] => return;
     *    13  => 9 9 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] => return;
     * --------------------------------------------------------------------------------------------
     *
     * @param array      数组
     * @param startIndex index开始的下标
     * @param endIndex   index结束的下标
     */
    private static void sort(int[] array, int startIndex, int endIndex) {

        String oldArray = Arrays.toString(array);
        // 递归结束条件，start>=end时，即结束递归
        if (startIndex >= endIndex) {
            System.out.printf("%s %s %s => return;\n", startIndex, endIndex, oldArray);
            return;
        }
        // 取得基准元素位置
        int pivotIndex = partition(array, startIndex, endIndex);
        String newArray = Arrays.toString(array);
        System.out.printf("%s %s %s => %s => %s\n", startIndex, endIndex, oldArray, newArray, pivotIndex);

        // 根据基准元素，对左右两个子数组进行递归排序
        sort(array, startIndex, pivotIndex - 1);
        sort(array, pivotIndex + 1, endIndex);
    }

    /**
     * 单边循环的核心思路，将所有比基准值小的值放在左侧
     *
     * @param array      数组
     * @param startIndex index开始的下标
     * @param endIndex   index结束的下标
     * @return 基准值交换之后的位置
     */
    private static int partition(int[] array, int startIndex, int endIndex) {
        // 比较基准值
        int pivot = array[startIndex];
        // 下标位置
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (array[i] < pivot) {
                // 需要注意，位置交换前，需要进行mark++
                // 所以如果基准值之后的所有值都小于基准值，这个for循环相当于什么都没做
                mark++;
                int p = array[mark];
                array[mark] = array[i];
                array[i] = p;
            }
        }
        array[startIndex] = array[mark];
        array[mark] = pivot;
        return mark;
    }


}
